<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    图 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						图
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/17 13:02 下午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E5%9F%BA%E6%9C%AC%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本术语</h2>
<ul>
<li>
<p>图：记为<code>G = (V, E)</code></p>
<ul>
<li>V是G的顶点集合（数据元素），是<strong>有穷非空集</strong></li>
<li>E是G的边集合（顶点之间的关系），是<strong>有穷集</strong></li>
</ul>
</li>
<li>
<p>有向图：图G中的每条边都是有方向的</p>
<ul>
<li>弧：有向图中带箭头的单向连线</li>
</ul>
</li>
<li>
<p>无向图：图G中的每条边都是无方向的</p>
</li>
<li>
<p>完全图：图G任意两个顶点都有一条边相连</p>
<ul>
<li>若n个顶点的无向图有<code>n(n - 1) / 2</code>条边，称为无向完全图</li>
<li>若n个顶点的有向图有<code>n(n - 1)</code>条边，称为有向完全图</li>
<li>G1的顶点集合为<code>V(G1) = {0, 1, 2, 3}</code></li>
<li>G1的边集合为<code>E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}</code></li>
</ul>
</li>
</ul>
<p><img src="media/16474933237825/16474947291757.jpg" alt="" /></p>
<ul>
<li>
<p>稀疏图：边较少的图，通常 <strong>边数 &lt;&lt; n<sup>2</sup></strong></p>
</li>
<li>
<p>稠密图：边很多的图</p>
<ul>
<li>无向图中，边数接近<code>n(n - 1) / 2</code></li>
<li>有向图中，边数接近<code>n(n - 1)</code></li>
</ul>
</li>
<li>
<p>子图：设有两个图<code>G = (V, E)</code>和<code>G' = (V', E')</code>，若<code>V' ⊆ V</code>且<code>E' ⊆ E</code>，则称图G'是图G的子图</p>
</li>
</ul>
<p><img src="media/16474933237825/16474955334202.jpg" alt="" /></p>
<ul>
<li>
<p>带权图：即边上带权的图，其中权是指每条边可以标上<strong>具有某种含义的数值</strong>（即与边相关的数），带权图 = 网络</p>
</li>
<li>
<p>邻接点：若<code>(u, v)</code>是E(G)中的一条边，则称u与v互为邻接顶点</p>
</li>
<li>
<p>弧头和尾：有向边<code>(u, v)</code>称为弧，弧的始点u叫弧尾，终点v（即箭头）叫弧头</p>
</li>
<li>
<p>度：顶点v的度是与它相关联的<strong>边的条数</strong>，记作TD(v)</p>
<ul>
<li>入度：以顶点v为<strong>终点</strong>（弧头指向v）的有向边的条数，记作ID(v)</li>
<li>出度：以顶点v为<strong>始点</strong>（弧尾指向v）的有向边的条数，记作OD(v)</li>
<li>当有向图中<strong>仅1个顶点的入度为0</strong>，其余顶点的入度均为1，这个有向图是一棵<strong>有向树</strong></li>
</ul>
</li>
</ul>
<p><img src="media/16474933237825/16474972398600.jpg" alt="" /></p>
<ul>
<li>
<p>连通图：在无向图中，若<strong>从顶点v<sub>1</sub>到v<sub>2</sub>有路径</strong>，则称顶点v<sub>1</sub>与v<sub>2</sub>是连通的，如果图中任意一对顶点都是连通的，则称此图是连通图</p>
<ul>
<li>连通分量：非连通图的<strong>极大连通子图</strong>叫做连通分量</li>
</ul>
</li>
<li>
<p>强连通图：在有向图中，若每一对顶点v<sub>i</sub>和v<sub>j</sub>，都存在一条<strong>从v<sub>i</sub>到v<sub>j</sub></strong> 和 <strong>从v<sub>j</sub>到v<sub>i</sub></strong> 的路径，则称此图是强连通图</p>
<ul>
<li>强连通分量：非强连通图的<strong>极大强连通子图</strong>叫做强连通分量</li>
</ul>
</li>
<li>
<p>生成树：是一个<strong>极小连通子图</strong>，它含有图中<strong>全部顶点</strong>，但只有<code>n - 1</code>条边，如果在生成树上添加1条边，必定构成一个环</p>
</li>
<li>
<p>若图中有n个顶点，却少于<code>n - 1</code>条边，必为非连通图</p>
</li>
<li>
<p>生成森林：<strong>由若干棵生成树组成</strong>，含全部顶点，但构成这些的数的边是最少的</p>
</li>
<li>
<p>路径：在图<code>G = (V, E)</code>中，若从顶点v<sub>i</sub>出发，沿一些边经过一些顶点<strong>v<sub>p1</sub>, v<sub>p2</sub>, ..., v<sub>pm</sub></strong>，到达顶点v<sub>j</sub>，则称顶点序列 <strong>(v<sub>i</sub> v<sub>p1</sub> v<sub>p1</sub> ... v<sub>pm</sub> v<sub>j</sub>)</strong> 是从v<sub>i</sub>到v<sub>j</sub>的路径，它经过的边 <strong>(v<sub>i</sub>, v<sub>p1</sub>)、(v<sub>p1</sub>, v<sub>p2</sub>)、... 、(v<sub>pm</sub>, v<sub>j</sub>)</strong> 应当是属于E的边</p>
</li>
<li>
<p>路径长度：非带权图的路径长度是指此路径上边的数量；带权图的路径长度是指路径上各边的权之和</p>
</li>
<li>
<p>简单路径：路径上各顶点<strong>v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>m</sub></strong> 均不互相重复</p>
</li>
<li>
<p>回路：若路径上第一个顶点v<sub>1</sub>与最后一个顶点v<sub>m</sub>重合，则称这样的路径为回路或环</p>
</li>
</ul>
<p><img src="media/16474933237825/16475097478696.jpg" alt="" /></p>
<h2><a id="%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>存储结构</h2>
<p>非线性结构（m : n）</p>
<h3><a id="%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序存储结构</h3>
<p>无，但可用数组描述元素间的关系</p>
<h4><a id="%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%EF%BC%88%E6%95%B0%E7%BB%84%EF%BC%89%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>邻接矩阵（数组）表示法</h4>
<p>建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间的关系）</p>
<h5><a id="%E4%BC%98%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>优点</h5>
<p>容易实现图的操作，如求某个顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等</p>
<h5><a id="%E7%BC%BA%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>缺点</h5>
<p>n个顶点需要n * n个单元存储边（弧），空间效率为<strong>O(n<sup>2</sup>)</strong>，对稀疏图而言尤其浪费空间</p>
<h5><a id="%E6%97%A0%E5%90%91%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>无向邻接矩阵</h5>
<p>设图A = (V, E)有n个顶点，则图的邻接矩阵是一个二维数组<code>A.Edge[n][m]</code>，定义为：</p>
<p><img src="media/16474933237825/16475188097610.jpg" alt="" /></p>
<ul>
<li>邻接矩阵存储的仅是图的邻接关系（即E），有邻接关系的结点为1，无邻接关系为0</li>
<li>无向图的邻接矩阵是对称的（横向和纵向完全一致）</li>
<li>顶点i的度 = 第i行（列）中1的个数，完全图的邻接矩阵中，对角元素为0，其余全部为1</li>
</ul>
<p><img src="media/16474933237825/16475109442931.jpg" alt="" /></p>
<h5><a id="%E6%9C%89%E5%90%91%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>有向邻接矩阵</h5>
<p>第i行：以结点v<sub>i</sub>为<strong>尾</strong>的弧（<strong>箭头指向的一边</strong>，即出度边）<br />
第i列：以结点v<sub>i</sub>为<strong>头</strong>的弧（<strong>没有箭头的一边</strong>，即入度边）</p>
<p><img src="media/16474933237825/16475192167182.jpg" alt="" /></p>
<ul>
<li>有向图的邻接矩阵<strong>可能</strong>是不对称的</li>
<li>顶点的出度：第i行元素之和 <strong>OD(V<sub>i</sub>) =</strong> <code>Σ A.Edge[i][j]</code></li>
<li>顶点的入度：第i列元素之和 <strong>ID(V<sub>i</sub>) =</strong> <code>Σ A.Edge[j][i]</code></li>
<li>顶点的度 = 第i行元素之和 + 第i列元素之和
<ul>
<li><strong>即：</strong> TD(V<sub>i</sub>) = OD(V<sub>i</sub>) + ID(V<sub>i</sub>)</li>
</ul>
</li>
</ul>
<h5><a id="%E7%BD%91%EF%BC%88%E5%8D%B3%E6%9C%89%E6%9D%83%E5%9B%BE%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>网（即有权图）</h5>
<p><img src="media/16474933237825/16475301977746.jpg" alt="" /></p>
<ul>
<li>有权值（有弧）则标注权值</li>
<li>无权值（无弧）则置为<strong>∞</strong></li>
</ul>
<p><img src="media/16474933237825/16475301424163.jpg" alt="" /></p>
<h3><a id="%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链式存储结构</h3>
<p>邻接表，邻接多重表，十字链表</p>
<h4><a id="%E9%82%BB%E6%8E%A5%E8%A1%A8%EF%BC%88%E9%93%BE%E5%BC%8F%EF%BC%89%E8%A1%A8%E7%A4%BA%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>邻接表（链式）表示法</h4>
<p>对每个顶点v<sub>i</sub>建立一个单链表，把与v<sub>i</sub><strong>有关联的边（弧）的信息</strong>（即度或出度边）链接起来，表中每个结点都设为3个域</p>
<p><img src="media/16474933237825/16475331142842.jpg" alt="" /></p>
<h5><a id="%E6%97%A0%E5%90%91%E9%82%BB%E6%8E%A5%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>无向邻接表</h5>
<ul>
<li>对于有n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点，空间效率为O(n + 2e)</li>
<li>若是稀疏图(e &lt;&lt; n<sup>2</sup>)，则比邻接矩阵表示法O(n<sup>2</sup>)省空间</li>
<li>无向图顶点的度 TD(v<sub>i</sub>) = 单链表中链接的结点个数</li>
</ul>
<p><img src="media/16474933237825/16475332160390.jpg" alt="" /></p>
<h5><a id="%E6%9C%89%E5%90%91%E9%82%BB%E6%8E%A5%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>有向邻接表</h5>
<p>分为存储出边的邻接表和存储入边的逆邻接表</p>
<ul>
<li>在有向图中，邻接表除了n个头结点外，只有e个表结点，空间效率为O(n + e)</li>
<li>若是稀疏图，则比邻接矩阵表示法合适</li>
<li>有向图的<strong>出度</strong> OD(v<sub>i</sub>) = 单链邻接表（出边表）中链接的结点数</li>
<li>有向图的<strong>入度</strong> ID(v<sub>i</sub>) = 邻接点为v<sub>i</sub>的弧个数<strong>或</strong>单链<strong>逆邻接表</strong>（入边表）中链接的结点数</li>
<li>有向图的度 TD(v<sub>i</sub>) = OD(v<sub>i</sub>) + ID(v<sub>i</sub>)</li>
</ul>
<h4><a id="%E5%8D%81%E5%AD%97%E9%93%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>十字链表</h4>
<p>适用于有向图</p>
<h4><a id="%E9%82%BB%E6%8E%A5%E5%A4%9A%E9%87%8D%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>邻接多重表</h4>
<p>适用于无向图</p>
<h3><a id="%E5%BC%82%E5%90%8C%E4%B9%8B%E5%A4%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>异同之处</h3>
<h4><a id="%E8%81%94%E7%B3%BB" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>联系</h4>
<ul>
<li>邻接表中每个链表对应于邻接矩阵中的一行，邻接表中的结点个数等于邻接矩阵一行中非零元素的个数</li>
</ul>
<h4><a id="%E5%8C%BA%E5%88%AB" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>区别</h4>
<ul>
<li>对于对于任意确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）</li>
<li>邻接矩阵的空间复杂度为O(n<sup>2</sup>)，邻接表的空间复杂度为O(n + e)</li>
</ul>
<h4><a id="%E7%94%A8%E9%80%94" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>用途</h4>
<ul>
<li><strong>邻接矩阵</strong>多用于<strong>稠密图</strong>的存储（e接近n(n - 1) / 2）</li>
<li><strong>邻接表</strong>多用于<strong>稀疏图</strong>的存储（e &lt;&lt; n<sup>2</sup>）</li>
</ul>
<p><img src="media/16474933237825/16475333684886.jpg" alt="" /></p>
<h2><a id="%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>图的遍历</h2>
<h3><a id="%E6%A6%82%E5%BF%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>概念</h3>
<h4><a id="%E9%81%8D%E5%8E%86%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历定义</h4>
<p>从已给的连通图中某一顶点出发，沿着一些边访问图中所有顶点，且使每个顶点仅被访问一次，就叫图的遍历，它是图的基本运算</p>
<h4><a id="%E9%81%8D%E5%8E%86%E5%AE%9E%E8%B4%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历实质</h4>
<p>找每个顶点的邻接点的过程</p>
<h4><a id="%E5%9B%BE%E7%9A%84%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>图的特点</h4>
<p>图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的顶点</p>
<h4><a id="%E9%81%BF%E5%85%8D%E9%87%8D%E5%A4%8D%E8%AE%BF%E9%97%AE" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>避免重复访问</h4>
<p>设置一个辅助数组 visited[n]，用来标记每个被访问过的顶点，它的初始状态为0，在图的遍历过程中，一旦某个顶点i被访问，就将visited[i]改为1，防止顶点i被多次访问</p>
<h3><a id="%E5%B8%B8%E7%94%A8%E9%81%8D%E5%8E%86%E6%96%B9%E5%BC%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>常用遍历方式</h3>
<h4><a id="%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%EF%BC%88dfs%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>深度优先遍历（DFS）</h4>
<ul>
<li>基本思想：仿树的先序遍历过程</li>
</ul>
<h5><a id="%E6%95%88%E7%8E%87%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>效率分析</h5>
<p>设图中有n个顶点，e条边</p>
<ul>
<li>如果用<strong>邻接矩阵</strong>来表示图，遍历图中每一个顶点都需要<strong>从头扫描该顶点所在行</strong>，因此遍历图的时间复杂度为O(n<sup>2</sup>)</li>
<li>如果用<strong>邻接表</strong>来表示图，虽然有2e个表结点，但只需要<strong>扫描e个结点</strong>即可完成遍历，加上<strong>访问n个头结点</strong>的时间，因此遍历图的时间复杂度为O(n + e)</li>
</ul>
<h5><a id="%E8%AE%BF%E9%97%AE%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>访问步骤</h5>
<ul>
<li>访问起始点v</li>
<li>若v的第一个邻接点没访问过，深度遍历此邻接点</li>
<li>若当前邻接点已经访问过，再找v的第二个邻接点重新遍历</li>
</ul>
<h5><a id="%E9%80%9A%E8%BF%87%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E8%AE%BF%E9%97%AE" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>通过邻接矩阵访问</h5>
<p><img src="media/16474933237825/16475984513143.jpg" alt="" /></p>
<table>
<thead>
<tr>
<th> </th>
<th><strong>1</strong></th>
<th><strong>2</strong></th>
<th><strong>3</strong></th>
<th><strong>4</strong></th>
<th><strong>5</strong></th>
<th><strong>6</strong></th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>1</strong></td>
<td>0</td>
<td><em>1</em></td>
<td><em>1</em></td>
<td><em>1</em></td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td><strong>2</strong></td>
<td><em>1</em></td>
<td>0</td>
<td>0</td>
<td>0</td>
<td><em>1</em></td>
<td>0</td>
</tr>
<tr>
<td><strong>3</strong></td>
<td><em>1</em></td>
<td>0</td>
<td>0</td>
<td>0</td>
<td><em>1</em></td>
<td>0</td>
</tr>
<tr>
<td><strong>4</strong></td>
<td><em>1</em></td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td><em>1</em></td>
</tr>
<tr>
<td><strong>5</strong></td>
<td>0</td>
<td><em>1</em></td>
<td><em>1</em></td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td><strong>6</strong></td>
<td>0</td>
<td>0</td>
<td>0</td>
<td><em>1</em></td>
<td>0</td>
<td>0</td>
</tr>
</tbody>
</table>
<ul>
<li>以顶点v2为起点，首先访问邻接表的<strong>第2行</strong></li>
<li>访问到<strong>第2行</strong>第一个邻接点时，顶点v1未被访问，跳转到邻接矩阵第1行</li>
<li>访问到<strong>第1行</strong>第一个邻接点时，顶点v2已被访问，访问第1行第二个邻接点，顶点v3未被访问，跳转到邻接矩阵第3行</li>
<li>访问到<strong>第3行</strong>，重复以上步骤，跳转到<strong>第5行</strong></li>
<li>访问到<strong>第5行</strong>的第一、二个邻接点，v2、v3均已访问，回到邻接矩阵<strong>第3行</strong></li>
<li><strong>第3行</strong>的无未被访问的邻接点，回到<strong>第1行</strong></li>
<li>访问到<strong>第1行</strong>的第三个邻接点时，顶点v4未被访问，跳转到<strong>第4行</strong>，之后<strong>重复以上步骤</strong></li>
</ul>
<h5><a id="%E9%80%9A%E8%BF%87%E9%82%BB%E6%8E%A5%E8%A1%A8%E8%AE%BF%E9%97%AE" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>通过邻接表访问</h5>
<p><img src="media/16474933237825/16475990203065.jpg" alt="" /></p>
<h5><a id="%E7%BB%93%E8%AE%BA%EF%BC%9A" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>结论：</h5>
<ul>
<li>稠密图适合在邻接矩阵上进行深度遍历</li>
<li>稀疏图适合在邻接表上进行深度遍历</li>
</ul>
<h4><a id="%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%EF%BC%88bfs%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>广度优先遍历（BFS）</h4>
<p>广度优先搜索是一种分层的搜索过程，每向前走一步可能需要访问一批顶点，不像深度优先搜索那样有回退的情况，因此，广度优先搜索不是一个递归的过程</p>
<ul>
<li>基本思想：仿树的层次遍历过程</li>
</ul>
<h5><a id="%E5%9F%BA%E6%9C%AC%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>基本实现</h5>
<ul>
<li>在访问起始点v后，依次访问v的邻接点</li>
<li>然后再依次访问这些顶点（<strong>v的邻接点</strong>）未被访问过的邻接点</li>
<li>直到所有顶点都被访问过</li>
</ul>
<p><img src="media/16474933237825/16476052161802.jpg" alt="" /></p>
<h5><a id="%E6%95%88%E7%8E%87%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>效率分析</h5>
<p>设图中有n个顶点，e条边</p>
<ul>
<li>如果使用邻接表来表示图，则BFS循环的总时间代价为：
<ul>
<li><strong>d<sub>0</sub> + d<sub>2</sub> + ... + d<sub>n - 1</sub> = O(e)</strong>（d<sub>i</sub>是顶点i的度）</li>
</ul>
</li>
<li>若使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的一整行，时间代价为<strong>O(n<sup>2</sup>)</strong></li>
</ul>
<h5><a id="%E8%AE%BF%E9%97%AE%E8%BF%87%E7%A8%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>访问过程</h5>
<ul>
<li>从v2开始访问，<strong>v2入队</strong></li>
<li><strong>v2出队</strong>，与v2有邻接关系的<strong>v1、v5依次入队</strong></li>
<li><strong>v1出队</strong>，与v1有邻接关系，但未被访问过的<strong>v3、v4依次入队</strong></li>
<li><strong>v5出队</strong>，与v5有邻接关系的顶点<strong>均被访问过</strong></li>
<li><strong>v3出队</strong>，与v3有邻接关系的顶点<strong>均被访问过</strong></li>
<li><strong>v4出队</strong>，与v4有邻接关系，但未被访问过的<strong>v6入队</strong></li>
<li><strong>v6出队</strong>，遍历结束</li>
</ul>
<p><img src="media/16474933237825/16476098793481.jpg" alt="" /></p>
<h4><a id="dfs%E4%B8%8Ebfs%E6%AF%94%E8%BE%83" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>DFS与BFS比较</h4>
<ul>
<li>空间复杂度相同，都是O(n)（借用了堆栈或队列）</li>
<li>时间复杂度只与存储结构（邻接表或邻接矩阵）有关，与搜索路径无关</li>
</ul>
<h2><a id="%E5%9B%BE%E7%9A%84%E5%85%B6%E4%BB%96%E8%BF%90%E7%AE%97" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>图的其他运算</h2>
<h3><a id="%E6%B1%82%E5%9B%BE%E7%9A%84%E7%94%9F%E6%88%90%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求图的生成树</h3>
<h4><a id="%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E7%89%B9%E8%AF%81" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>生成树的特证</h4>
<p>n个顶点的连通网络的生成树有n个顶点、n - 1条边</p>
<h4><a id="%E6%B1%82%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E6%96%B9%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求生成树的方法</h4>
<p>深度优先搜索（DFS）和广度优先搜索（BFS）</p>
<ul>
<li>对于连通图，仅需从图中任一顶点出发，进行DFS或BFS，便可访问到图中所有顶点</li>
<li>对于非连通图，需要<strong>从多个顶点出发</strong>进行搜索，而每一次从一个新的起始点出发进行搜索的过程中得到的<strong>顶点访问序列</strong>恰为其<strong>各个连通分量中的顶点集</strong></li>
</ul>
<h3><a id="%E6%B1%82%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求最小生成树</h3>
<h4><a id="%E7%9B%AE%E6%A0%87" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>目标</h4>
<p>在网的多个生成树中，寻找一个各边权值之和最小的生成树</p>
<h4><a id="%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法</h4>
<h5><a id="kruskal%EF%BC%88%E5%85%8B%E9%B2%81%E6%96%AF%C2%B7%E5%8D%A1%E5%B0%94%EF%BC%89%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Kruskal（克鲁斯·卡尔）算法</h5>
<p>归并边，时间复杂度为O(e log<sub>2</sub>e)</p>
<ul>
<li>找到<strong>权值最小</strong>的边，使其两端的顶点相连</li>
<li>找出下一个权值最小的边，但找到的边<strong>不能使生成树形成环</strong>，重复该步骤</li>
</ul>
<h5><a id="prim%EF%BC%88%E6%99%AE%E9%87%8C%E5%A7%86%EF%BC%89%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>Prim（普里姆）算法</h5>
<p>归并顶点，时间复杂度为O(n<sup>2</sup>)</p>
<ul>
<li>选中一个顶点</li>
<li>找到和第一个顶点<strong>有邻接关系且权值最小</strong>的顶点</li>
<li>找到与已选择的顶点有邻接关系、<strong>没有被选择过</strong>且权值最小的顶点，重复该步骤</li>
</ul>
<p><img src="media/16474933237825/16476231406431.jpg" alt="" /></p>
<h4><a id="%E6%AF%94%E8%BE%83" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>比较</h4>
<ul>
<li>求<strong>稀疏图</strong>的最小生成树用Kruskal算法</li>
<li>求<strong>稠密图</strong>的最小生成树用Prim算法</li>
</ul>
<h3><a id="%E6%B1%82%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求最短路径</h3>
<h4><a id="%E6%8A%BD%E8%B1%A1%E6%A6%82%E5%BF%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>抽象概念</h4>
<p>在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径</p>
<h4><a id="%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E2%80%94%E2%80%94dijkstra%EF%BC%88%E8%BF%AA%E6%9D%B0%E6%96%AF%E7%89%B9%E6%8B%89%EF%BC%89%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>单源最短路径——Dijkstra（迪杰斯特拉）算法</h4>
<p>设一有向图<code>G = (V, E)</code>，已知各边的权值，以某指定点v<sub>0</sub>为源点，求从v<sub>0</sub>到图的其余各店的最短路径，限定各边上的权值大于或等于0</p>
<p><img src="media/16474933237825/16476240461555.jpg" alt="" /></p>
<ul>
<li>从起点v<sub>0</sub>出发，找到v<sub>0</sub>到其它邻接点的权值，并记录下权值最小的邻接点</li>
<li>权值最小的邻接点出发，找到该邻接点到其它邻接点的权值，再次记录下权值最小的邻接点</li>
<li>重复以上步骤，直到找到v<sub>0</sub>到各终点的最短路径和权值</li>
</ul>
<p><img src="media/16474933237825/16476244195682.jpg" alt="" /></p>
<table>
<thead>
<tr>
<th>源点</th>
<th>终点</th>
<th>最短路径</th>
<th>路径长度</th>
</tr>
</thead>
<tbody>
<tr>
<td>v<sub>0</sub></td>
<td>v<sub>1</sub></td>
<td>(v<sub>0</sub>, v<sub>1</sub>)</td>
<td>10</td>
</tr>
<tr>
<td> </td>
<td>v<sub>2</sub></td>
<td>(v<sub>0</sub>, v<sub>1</sub>, v<sub>2</sub>) (v<sub>0</sub>, v<sub>3</sub>, v<sub>2</sub>)</td>
<td>60 50</td>
</tr>
<tr>
<td> </td>
<td>v<sub>3</sub></td>
<td>(v<sub>0</sub>, v<sub>3</sub>)</td>
<td>30</td>
</tr>
<tr>
<td> </td>
<td>v<sub>4</sub></td>
<td>(v<sub>0</sub>, v<sub>4</sub>) (v<sub>0</sub>, v<sub>3</sub>, v<sub>4</sub>) (v<sub>0</sub>, v<sub>1</sub>, v<sub>2</sub>, v<sub>4</sub>)</td>
<td>100 90 70</td>
</tr>
</tbody>
</table>
<h4><a id="%E6%89%80%E6%9C%89%E9%A1%B6%E7%82%B9%E9%97%B4%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E2%80%94%E2%80%94floyd%EF%BC%88%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%EF%BC%89%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>所有顶点间最短路径——Floyd（弗洛伊德）算法</h4>
<p>已知一个各边权值均大于0的带权有向图，对每一个顶点（v<sub>i</sub>, v<sub>j</sub>），希望求出v<sub>i</sub>与v<sub>j</sub>之间的最短路径和最短路径长度</p>
<ul>
<li>可以通过调用n次Dijkstra算法来完成，但时间复杂度为O(n<sub>3</sub>)</li>
<li>改进算法：<strong>Floyd算法</strong></li>
</ul>
<h2><a id="%E5%9B%BE%E7%9A%84%E5%BA%94%E7%94%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>图的应用</h2>
<h3><a id="%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>拓扑排序</h3>
<h4><a id="aov%E7%BD%91%EF%BC%88activity-on-vertices%EF%BC%89%E2%80%94%E2%80%94%E7%94%A8%E9%A1%B6%E7%82%B9%E8%A1%A8%E7%A4%BA%E6%B4%BB%E5%8A%A8%E7%9A%84%E7%BD%91%E7%BB%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>AOV网（Activity On Vertices）——用顶点表示活动的网络</h4>
<p>定义：</p>
<ul>
<li>若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系，V<sub>i</sub>必须先于活动V<sub>j</sub>进行，则这样的有向图叫做用顶点表示活动的网络，简称AOV网</li>
</ul>
<p>拓扑有序序列：<strong>V<sub>6</sub> - V<sub>1</sub> - V<sub>4</sub> - V<sub>3</sub> - V<sub>2</sub> - V<sub>5</sub></strong></p>
<ul>
<li>输入AOV网络，令n为顶点个数</li>
<li>在AOV网络中选择一个<strong>没有直接前驱的顶点</strong>并输出</li>
<li>将选中的<strong>顶点及其发出的有向边</strong>从图中删除</li>
<li>选择下一个没有直接前驱的顶点</li>
<li>循环以上步骤，直到循环结束</li>
<li>若全部顶点均已输出，拓扑有序序列形成，拓扑排序完成</li>
<li>若循环结束时图中还有未输出的顶点，说明AOV网络中存在有向环</li>
</ul>
<p><img src="media/16474933237825/16476952509946.jpg" alt="" /></p>
<p><strong>注意：</strong> 拓扑排序结果不唯一，从不同的顶点开始排序可以得到不同的结果<br />
<img src="media/16474933237825/16476951298671.jpg" alt="" /></p>
<h4><a id="aoe%E7%BD%91%EF%BC%88activity-on-edge%EF%BC%89%E2%80%94%E2%80%94%E7%94%A8%E8%BE%B9%E8%A1%A8%E7%A4%BA%E6%B4%BB%E5%8A%A8%E7%9A%84%E7%BD%91%E7%BB%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>AOE网（Activity On Edge）——用边表示活动的网络</h4>
<p>定义：</p>
<ul>
<li>如果在无环的带权有向图中，用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称AOE网</li>
<li>在AOE网中有些活动可以并行的进行，故完成工程的最短时间是从开始点到完成点的最长路径长度，即关键路径的长度</li>
</ul>
<p>基本术语：</p>
<ul>
<li>源点：入度为0的点（工程的开始点，只有一个）</li>
<li>汇点：出度为0的点（工程的完成点，只有一个）</li>
<li>路径长度：指路径上各活动持续时间之和（即<strong>权值之和</strong>）</li>
<li>关键路径：路径长度<strong>最长</strong>的路径</li>
<li>关键活动：满足l(s) = e(s)的活动as</li>
</ul>
<p><img src="media/16474933237825/16476962192275.jpg" alt="" /></p>
<ul>
<li>因为关键路径上的活动都是关键活动，，所以提前完成非关键活动并不能加快工程的进度</li>
</ul>
<p>要在最短时间内完成一项工程，需要做一下工作：</p>
<ul>
<li>画出该工程各个子工程的有向无环网络</li>
<li>求出各个顶点（即事件）的ve和vl 并找到关键路径</li>
<li>根据各顶点的Ve和Vl值，求出每条弧s上活动的e(s)和l(s)，由此找到关键活动</li>
</ul>
<h3><a id="%E6%B1%82%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>求关键路径</h3>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  






















</body>

</html>